'''
https://leetcode.cn/problems/divide-chocolate
'''
from typing import List


class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        def f(limit):
            res = 0
            cur = 0
            for num in sweetness:
                cur += num
                if cur >= limit:
                    res += 1
                    cur = 0
            return res

        l = 0
        r = sum(sweetness) // (k + 1)
        res = 0
        while l <= r:
            mid = l + r >> 1
            n_chunk = f(mid)
            if n_chunk > k:     # >= k+1
                res = mid
                l = mid + 1
            else:
                r = mid - 1
        return res
